package cn.datastruct.five;
/*
*   插入排序：
*       1、分为有序和无序两个表
*       2、从无序表中去第一个元素和有序表的最后一个元素开始，依次比较，找到合适的位置插入
* */
public class InsertSort {
    public static void insertSort(int[] arr){
        //数组长度
        int length = arr.length;
        int arrval;
        for (int i = 1; i < length; i++) {
            arrval = arr[i];
            int j=0;
            for (j = i; j >= 0; j--) {
                if(arrval < arr[j]){//如果比前一个数小，则交换
                    arr[j + 1] = arr[j];
//                    arr[j] = arr[j] ^ arr[j - 1];
//                    arr[j - 1] = arr[j] ^ arr[j - 1];
//                    arr[j] = arr[j] ^ arr[j - 1];
                }
                if(arrval > arr[j]){
                    break;
                }
            }
            arr[j + 1] = arrval;
        }
    }

    public static void main(String[] args) {
        int[] arr = {-1,-10, -2, -12};
        insertSort(arr);
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            System.out.printf("%d\t", arr[i]);
        }
    }
}
